'''
    该文件用来模拟创建动态集合 
    模拟Java 中的ArrayList 
    https://labuladong.online/algo/data-structure-basic/array-implement/
'''
class MyArrayList:
    INIT_CAP = 1
    def __init__(self,init_capacity=None):
        # 初始化默认数组 
        self.data =[None] * (init_capacity if init_capacity is not None else self.__class__.INIT_CAP)
        self.size = 0
        
    # 增加
    def add_last(self,e):
        # 判断容量是不是超标
        cap =len(self.data)
        if self.size == cap :
            self._resize(2*cap)
        self.data[self.size] = e
        self.size+=1

    # 添加元素 
    def add(self,index,e):
        # 检查索引是不是超过索引 
        self._check_position_index(index)
        cap =len(self.data)
        if self.size ==cap:
            self._resize(2*cap)
        # 从后向前
        for i in range(self.size -1 ,index-1,-1):
            self.data[i+1] = self.data[i]
        self.data[index] = e
        self.size+=1
    
    def add_first(self,e):
        self.add(0,e)

    # 删除最后一个数据 
    def remove_last(self):
        if self.size ==0 :
            raise Exception
        cap  = len(self.data)
        if self.size ==cap // 4 :
            self._resize(cap//2)
        delete_val = self.data[self.size-1]
        self.data[self.size-1] = None
        return delete_val
    
    def remove(self,index):
        self._check_position_index(index=index)
        cap = len(self.data)
        # 可以缩容
        if self.size == cap//4:
            self._resize(cap//2)
        delete_val = self.data[index]
        for i in range(index+1,self.size) :
            self.data[i-1] =self.data[i]
        self.data[self.size-1] = None
        self.size -=1
        return delete_val
    def remove_first(self):
        return self.remove(0)
    def get(self,index):
        self._check_position_index(index)
        return self.data[index]
    def size(self) :
        return self.size
    def is_empty(self):
        return self.size ==0
    
        

    # 扩容 
    def _resize(self,new_cap):
        temp =[None]* new_cap
        for i in range(self.size):
            temp[i] = self.data[i]
        self.data = temp
    


    def display(self):
        print(f"size = {self.size},cap={len(self.data)}")
        print(self.data)
    def _check_position_index(self,index):
        if not self._is_positon_index(index) :
            raise IndexError(f"Index:{index} ,Size :{self.size}")
    
    # 检查资源是不是越界 
    def _is_positon_index(self,index):
        return 0<=index<=self.size
    

if __name__ == '__main__':
    arr = MyArrayList(init_capacity=6)
    for i in range(1,6):
        arr.add_last(i)
    arr.display()
    arr.add(2,100)
    arr.display()

    

